#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    bool verifyTreeOrder(vector<int>& postorder)
    {
        int n = postorder.size();
        return _veifyTreeOrder(postorder, 0, n - 1);
    }

private:
    bool _veifyTreeOrder(const std::vector<int>& postorder, int left, int right)
    {
        if (left > right) {
            return true;
        }

        int rootVal = postorder[right];
        int end = right - 1;

        while (end >= left && postorder[end] > rootVal) {
            --end;
        }

        for (int i = end; i >= left; --i) {
            if (postorder[i] >= rootVal) {
                return false;
            }
        }

        bool isLeft = _veifyTreeOrder(postorder, left, end);
        if (isLeft == false) {
            return false;
        }

        bool isRight = _veifyTreeOrder(postorder, end + 1, right - 1);
        if (isRight == false) {
            return false;
        }

        return true;
    }
};